#ifndef QUICKSORT_H_
#define QUICKSORT_H_

#include <iostream>

using namespace std;

int Partition(int* arr, int lowIndex, int highIndex)
{
	int compareData = arr[lowIndex];
	int low = lowIndex;
	int high = highIndex + 1;
	while(true)
	{
		while(++low < highIndex && arr[low] < compareData);
		while(--high > lowIndex && arr[high] > compareData);
		if(low >= high)
		{
			break;
		}
		else
		{
			int temp = arr[low];
			arr[low] = arr[high];
			arr[high] = temp;
		}
	}
	arr[lowIndex] = arr[high];
	arr[high] = compareData;
	return high;
}	

void QuickSort(int* arr, int lowIndex, int highIndex)
{
	if(lowIndex < highIndex)
	{
		int tx = Partition(arr, lowIndex, highIndex);
		QuickSort(arr, lowIndex, tx - 1);
		QuickSort(arr, tx + 1, highIndex);
	}
}
#endif  // QUICKSORT_H_